package com.guaoran.algorithm.two.pointer;

/**
 * @Auth gucheng
 * @Desc 存水问题
 * https://leetcode.com/problems/trapping-rain-water/
 * @Date 2021/1/18 下午3:47
 */
public class TrappingRainWater {
    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap(height));
    }

    public static int trap(int[] height) {
        if(height == null || height.length == 0){
            return 0;
        }

        int sum = 0;
        int left = 0;
        int right = height.length -1;
        int leftHeight = height[left];
        int rightHeight = height[right];
        while(left < right){
            if(leftHeight < rightHeight){
                if(leftHeight > height[left+1]){
                    sum += (leftHeight - height[left +1]);
                }else {
                    leftHeight = height[left+1];
                }
                left ++;
            }else {
                if(rightHeight > height[right-1]){
                    sum += (rightHeight - height[right-1]);
                }else {
                    rightHeight = height[right-1];
                }
                right --;
            }
        }
        return sum;
    }
}
